% Homework 2
\documentclass[a4paper]{article}
\usepackage[hmargin=3cm,vmargin=3cm]{geometry}
\usepackage[mathcal]{euscript}
\begin{document}
\title{Answer Set \#2}
\author{Aditya Joshi (aj7645)}
\date{}
\maketitle
\subsection*{Homework Information}
Homework discussed with: Namrata Baliga \\
Slip days used (this homework): 2\indent Slip days used (total): 2

\subsection*{Answer 1}

Consider the modified algorithm where a process halts if it does not see any new failures in a
round.

\begin{verbatim}
Let faulty(p,k) be the set of processes that have failed to send a message to
p in any round (1..k)
1: if p := sender then value := m else value:= ? 
Process in round k, 1<=k<=f+1
2 : send value to all 
3 : if value != ? and delivered m in round k-1 then halt 
4 : receive round k values from all 
5 : faulty(p,k) := faulty(p, k−1) U {q | p received no value from q in round k} 
6 : if received value != ? then 
7 :     value := v 
8 :     deliver value 
9 : else if k=f+1 or |faulty(p,k)| = |faulty(p,k-1)| then  
10:     value := SF 
11:     deliver value 
12:     if k=f+1 then halt
\end{verbatim}

\subsubsection*{Proving t-tolerant TRB for Crash Failure}
Following is the proof for the above algorithm of being a t-tolerant early stopping TRB protocol 
for crash failures.\\

\textbf{Validity:} If the sender is correct and broadcasts a message $m$, then all correct processes 
eventually deliver $m$.\\

A message $m$ from a correct sender will be received by every correct process at the end of round 1. 
This is possible as the underlying $send$ and $receive$ ensure that once the message has been sent 
it will be received by a correct process in that round itself. So, on receiving a non '?' value the correct process will deliver $m$
in the round 1.  
\\

\textbf{Integrity:} Every correct process delivers at most one message, and if it delivers $m != SF$ , then some
process must have broadcast $m$\\

The algorithm above shows that each process delivers $atmost$ one message and then halts. The delivered message  
could either be $SF$ or $m$ depending upon the sender action in round 1. For a process $p$ to deliver
$m$ in a round $r != 1$ it must have heard the value from some other process $q$. This way we can form a 
chain backwards that terminates at the sender $s$ that broadcast $m$.\\

  
\textbf{Agreement:} If a correct process delivers a message m,
 then all correct processes eventually deliver m\\

We need to prove that, a message delivery decision reached when no new failures are heard, does not break
the correctness of the TRB. Let us assume that a process does not hear any new faults in two consecutive
rounds. This implies that, by the validity of the underlying send and receive, it has heard all the processes
and their respective values in the system. So if for two such consecutive rounds it hears '?' it knows that 
there is no other message (different) that it can hear in the future rounds. So this is as good as any round to 
decide $SF$ as none of the correct processes in the system at that time have heard $m$. Also, there can be no
round where a process decides $SF$ and another process decides $m$. This is proved as follows. Consider 
a round $k$ when process $p$ decides $m$ and process $q$ decides $SF$. For process $p$ to decide $m$ it either heard
$m$ from the sender in round 1 or $m$ was relayed to it by some other process. For $q$ to decide $SF$ it must have gone through
two consecutive rounds (say $i,j$)  not hearing any value (it heard only $'?'$). This is a contradiction as, if $p$ had heard the value $m$ 
in round $i$ it would have broadcast $m$ in round $j$. Channels being reliable $q$ is bound to have heard $m$ in round $j$. 
So no two processes can in the same round deliver different messages.  \\

\textbf{Termination:} Every correct process eventually delivers some message\\

The algorithm ends either when the protocol has run f+1 rounds or when it has witnessed two consecutive
rounds with no new failures. In either cases the protocol terminates and the process delivers some
message, either $SF$ or $m$.\\

\subsubsection*{Proving not t-tolerant TRB for Send Omission}
We can disprove the correctness of the above algorithm in the realm of send omission. By definition 
a process exhibits send omission when a process sends a message to, part or none of intended 
processes. Consider a case where the sender $s$, of message $m$, is the process exhibiting send omission. 
In \textbf{Round 1}, $s$ sends $no$ message to any process. All processes in the system set
their $|faulty(p, 1)| = 1$. Consider that in \textbf{Round 2}, the sender now sends $m$ to a subset 
of the processes and their are no other faults. Those receiving $m$ will deliver $m$. The processes not lucky enough to get $m$
will set their $|faulty(p, 2)| = 1$. For the set of processes not receiving $m$, no new faults have 
occurred. So, they will now conclude that the sender is faulty, deliver $SF$ and exit the protocol. We now have a 
situation where some correct processes deliver $m$ and some correct deliver $SF$. This violates the 
\textbf{Agreement} property of TRB protocols.

\newpage

\subsection*{Answer 2}

Consider an algorithm that solves Terminating Reliable Broadcast (TRB) in $f+2$ rounds. In round one 
it sends a message to all processes. After that a $f+1$ round consensus algorithm is employed. 
\begin{verbatim}
/* Sender s in round 1*/
1:send m to all

/* Receivers in round 1 */
/* Trivially, val for s will be m */
1:  receive m from s
2:  If m is received, val = m else val = SF .

/* CONSENSUS */
/* For the next f+1 rounds each process i executes the following */
Initially V = {val}
Execute propose(v)
    round k, 1<=k<=f+1
1:  send val to all
2:  for all j, 0<=j<=n-1, j != i  do
3:      receive val from process j
4:      V := V U val

/* Process decide the consensus value as */
decide(x):
5:  if k = f+1 then
6:      decide the value in V
\end{verbatim}

\subsubsection*{Consensus Requirements}
The underlying consensus algorithm is assumed to satisfy the following requirements

\textbf{Validity:} If all processes that propose a value propose v, then all correct processes
eventually decide v

\textbf{Agreement:} If a correct process decides v, then all correct processes eventually decide v

\textbf{Integrity:} Every correct process decides at most one value, and if it decides v, then 
some process must have proposed v

\textbf{Termination:} Every correct process eventually decides some value

\subsubsection*{Proving TRB}

Following is the proof that the above algorithm solves TRB: \\

\textbf{Validity:} If the sender is correct and broadcasts a message m, then all correct 
processes eventually deliver m.\\

Given a correct sender it will broadcast message $m$. The protocol assumes only crash failures, so 
in event of a correct sender only $m$ will be sent. The underlying $send$ and $receive$ ensure
that once $m$ is broadcast by the sender, all correct process will obtain $m$. This concludes 
$Round 1$. $Round 2$ onwards we have a $f+1$ round consensus algorithm that by the validity
condition will lead to all correct processes deciding $m$ and therefore delivering $m$.
\\   

\textbf{Agreement:} If a correct process delivers a message $m$, then all correct processes 
eventually deliver $m$.\\

For a process to deliver a message $m$, it has to be the consensus value. By the agreement 
property of the consensus algorithm it would mean that $m$ is delivered by all correct processes. So a 
process can only deliver a consensus value same as all the other processes in the system.
\\

\textbf{Integrity:} Every correct process delivers at most one message, and if it delivers $m != SF$ , 
then some process must have broadcast $m$.\\

Given that at the end of the consensus algorithm only one value will be chosen implies that every
correct process will consequently deliver $atmost$ one message. For a process to deliver $m$ which is
also the consensus message it has to be proposed by some process in the system. This follows from
the integrity property of the consensus algorithm. By the algorithm given this is the $m$ that
would have been broadcast by the sender in $Round 1$. The algorithm maintains the channel
$send$ and $receive$ property so message $m$ will be received by all correct process at the end of 
$Round 1$. From there it will be proposed and eventually delivered after $f+1$ rounds.
\\

\textbf{Termination:} Every correct process eventually delivers some message.\\

Each process delivers either $SF$ or $m$. If the sender does not broadcast anything then the 
processes at the end of the consensus algorithm will deliver $SF$. If a message $m$ was indeed 
broadcast then the processes will run the consensus algorithm with $m$ and at the end of round 
$f+1$ deliver $m$.
\\

\newpage

\subsection*{Answer 3}

The Uniform Agreement property for a Terminating Reliable Broadcast states that, 
If any process (whether correct or faulty) delivers a message $m$, then all correct processes eventually 
deliver $m$.\\

To achieve uniform TRB we delay delivering of messages right until the end. So, after $t+1$ rounds of 
message exchange the protocol goes through an additional round to ascertain the majority of the 
messages about to be delivered in the system. The protocol works on the assumption that majority (maybe simple)
of the processes are not faulty. So if a correct process receives $j>n/2 $ $m's$ it (and other alive correct processes) can safely
deliver $m$. Otherwise a $SF$ is delivered.
Delaying the message delivery after accounting for the $t$ crashes allows processes to deliver the same value
as decided by majority correct processes.

\begin{verbatim}
1:  Every process p executes the following algorithm:
2:  if process = sender then val = m else val =?
3:  for round k, 1 <= k <= t + 1
4:      Send val to all
5:      if val = m then break;
6:      receive round k messages;
7:      if received some message m != '?' then	val = m 

\end{verbatim}

By now we have all processes ready to deliver some $m$ or ready to decide $SF$. In order to ensure that all 
processes (correct and faulty) decide the same we need another round for the processes to exchange their
intentions.

\begin{verbatim}
1:  Send val to all processes;
2:  Receive round t + 2 values from all.
3:  if received majority (atleast simple) values of message m
4:      deliver m
5:  else
6:  if received majority (atleast simple)  values as ’?’
7:      then deliver SF
8:  halt
\end{verbatim}


\subsubsection*{Proving the algorithm}
Proof for uniform TRB\\

\textbf{Validity:} If the sender is correct and broadcasts a message $m$, then all correct processes eventually deliver $m$.\\

When a correct sender broadcasts $m$ in round 1 it will be heard by all the correct processes. This 
follows from the validity of the underlying channel. The processes hearing this value will now be part of the
majority required for all processes to decide $m$. As, the protocol assumes that a majority of the processes
are not faulty we will have the correct processes sending $m$ in round $f+2$ leading to all correct alive processes in the
system to deliver $m$.
\\

\textbf{Uniform agreement:} If any process (correct or faulty) delivers a
message $m$, then all correct processes eventually deliver $m$\\

For uniform agreement to fail some processes have to deliver $m$ and others have to deliver $SF$. This cannot happen in the algorithm suggested.\\

Case 1 - $p$, a non-faulty process, delivers $m$. For process $p$ to deliver $m$ it has to hear a majority of $m$ messages in round $t+2$. Simultaneously 
a correct process $q$ heard a majority of '?'. This means that one process sent '?' to $q$ and $m$ to $p$. 
As there are no byzantine faults we can conclude that the once a correct process delivers $m$ all correct processes will deliver $m$. \\

Case 1 - $p$, a faulty process, delivers $m$. For a faulty process $p$ to deliver $m$ it has to hear a majority of $m$ messages in round $t+2$. The process 
could be behaving faulty in previous rounds but when it decides to deliver $m$ there must have been a majority of $m$ that it obtained. So all correct processes, 
who would have also heard the $same$ majority, will deliver $m$.
 \\

\textbf{Integrity:} Every correct process delivers at most one message, and if it decides $m != SF$ , then some process must have broadcast $m$.\\

Each correct process delivers $atmost$ one message, either $m$ or $SF$ based on the majority it sees.
For a correct process to deliver $m != SF$ at the end of $t+2$ rounds it must have heard a
majority of $m$ messages in that round. For a majority of $m$ to exist after round $t+2$, more than half of the
processes must have $m$ with them in round $t+1$. For them to have $m$, either they obtained it directly from the sender 
or via a chain of other processes. In either case $m$ had to be broadcast in round 1 for processes to have it
by round $f+1$.\\

\textbf{Termination:} Every correct process eventually delivers some message\\

At the end of round $t+2$ all the alive correct process will reach a common decision and deliver either $m$ 
or $SF$ based on the majority of the values heard. This is possible due to the fact that reliable channels ensure that $m$ sent in $t+2$ round will be received in the
same round. There could be processes though that do not terminate after $f+2$ rounds as they exhibit
general omission and thus, are faulty. As the termination condition governs for only correct 
processes it is not mandatory for faulty processes to terminate.

\subsubsection*{No Uniform TRB where n $\le$ 2t} 
Following is the proof that there is no protocol solving the Uniform TRB problem in a synchronous 
system where up to $t \ge n/2$ processes can commit omission failures.\\


\textbf{Proof by contradiction:} Let us assume that there is a protocol that solves the uniform 
TRB in presence of up to $t \ge n/2$ faulty processes. 

Let us partition the processes in the system in two disjoint sets $P_0$ and $P_1$ such that $P_0$ includes t 
processes (including the sender), and $P_1$ includes the other $n-t$ processes. Consider the following execution:\\
Let processes in $P_0$ be correct and all processes in set $P_1$ be faulty. Processes in $P_1$ 
send and receive all messages within the set $P_1$. They however do neither receive (receive omission)
nor send messages (send omission) with respect to  processes in set $P_0$. 
When the sender in $P_0$ sends a message $m$, all in $P_0$ receive the message. Processes in $P_1$
oblivious to the send event of $m$ (receive omission) obtain nothing. In the next round all 
processes broadcast their received value. Processes in $P_0$ send $m$ to all processes. Processes in $P_1$ send to each other $'?'$  as they
exhibit receive omission from processes in $P_0$.  When the protocol ends, processes in $P_1$ have still not heard 
a value and consequently deliver $SF$. Processes in $P_0$ on the other hand deliver the first valid
message, ie $m$. This violates uniform agreement because some  faulty processes delivered $SF$ 
and the correct processes delivered $m$. Hence there exists no algorithm.

\newpage

\subsection*{Answer 4}

\subsubsection*{System Model}


The History system $\mathcal{H}$ is an asynchronous system with $n_s$ servers and two clients. 
$\mathcal{H}$ records all the $REQUEST's$ it sees and responds with the $sequence$ of values it has seen as yet. 
The system can tolerate one crash failure. In order for  $\mathcal{H}$ to always be able to respond
to client requests, some form of fault tolerance is assumed. Trivially, if $n_s = 1$ then $n_s$ 
can never crash. The goal is to achieve consensus employing $\mathcal{H}$.
\subsubsection*{Proposing Values}

Processes propose values by using the $REQUEST(c,op)$ method. Where $op$ is the value
client $c$ wants to propose. The history system keeps track of all the values proposed yet. Servers also
act as clients and invoke the $REQUEST(c,op)$ method to propose their values. The domain
of $op$ is assumed to be the characters in the range $(a, z)$. 

\subsubsection*{Deciding Outcome}
Given a sequence of characters, let a string $sequence$ denote their concatenation.
Let an deterministic function $HEAD(sequence)$ return the first value of the sequence, ie,
the first character at the head of the sequence. So, for $sequence = "abcd"$, $HEAD(sequence)$ 
returns $a$.

\subsubsection*{The Algorithm}

Each proposer executes the following algorithm to propose and decide on a value.\\

\begin{verbatim}
function consensus():
    res = REQUEST(c,op)       /* request with proposal op and block till response arrives */
    decision := HEAD(res)     /* obtain the consensus value */
        
\end{verbatim}

The algorithm essentially decides the first proposal recorded by the history system as the consensus value.

\subsubsection*{Proving Consensus}


\textbf{Validity:} If all processes that propose a value  propose v, then all correct processes
eventually decide v. \\

A proposal completes when the history system gets a request for it. As channels are 
reliable the requests will eventually reach the history servers and subsequent responses will
eventually reach the respective clients. Once the server has heard of
the request it is now permanently recorded in the system. The subsequent responses to the 
clients will contain all the proposed values seen by the system. So once a 
value has been proposed the processes will choose a value. \\

\textbf{Agreement:} If a correct process decides v, then all correct processes eventually decide 
v.\\

In the given system each process can determine the consensus value based the response received to
its proposal. The History servers act as recorders of all values proposed in the system. So $no$ 
process can decide a value that was not proposed. Also, given the fact that if history system 
returns responses $sequence_1$ and $sequence_2$ to clients $c_1$ and $c_2$. Then either $sequence_1$ 
is the prefix of $sequence_2$ or vice versa. Each correct client invoking the $HEAD$ function on the
response will decide on the same consensus value.\\

\textbf{Integrity:} Every correct process decides at most one value, and if it decides v, then some
process must have proposed v\\

The decision is based on the $HEAD(sequence)$ result. This can only return one value so each process will
decide $atmost$ one value. Also for a value to be part of the $sequence$ it has to be proposed by some process
in the system. As, the history system records only the proposals of the system and $no$ other value,
the $sequence$ will always contain the proposed set of values. So, $HEAD(sequence)$ will always return a 
single value that has been proposed. \\

 
\textbf{Termination:} Every correct process eventually decides some value \\

The algorithm terminates as soon as a process gets response to its proposal. The history system has to
send a response to the client irrespective of a server crash. So no client is forever waiting for the 
server to respond. Given that the 
system has only one crash failure, at least one value will be proposed by the system. Also, the 
clients do have to wait for all other processes to propose their values in order to arrive at the 
decision. So, timing of other proposals has no impact on the termination. The processes will decide even 
if one of the process proposes a value.\\
Hence the solution solves Consensus for a single crash failure.


\end{document}
